//给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
//
// 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
//
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
//
//
//
// 示例 1：
//
//
//输入：k = 2, prices = [2,4,1]
//输出：2
//解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
//
// 示例 2：
//
//
//输入：k = 2, prices = [3,2,6,5,0,3]
//输出：7
//解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
//     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3
//。
//
//
//
// 提示：
//
//
// 0 <= k <= 100
// 0 <= prices.length <= 1000
// 0 <= prices[i] <= 1000
//
//
// Related Topics 数组与矩阵 动态规划 👍 924 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function maxProfit(k: number, prices: number[]): number {
    /*
    本题和动态规划：123.买卖股票的最佳时机III (opens new window)最大的区别就是这里要类比j为奇数是买，偶数是卖的状态。
    使用二维数组 dp[i][j] ：第i天的状态为j，所剩下的最大现金是dp[i][j]
    大家应该发现规律了吧 ，除了0以外，偶数就是卖出，奇数就是买入。
    题目要求是至多有K笔交易，那么j的范围就定义为 2 * k + 1 就可以了
    还要强调一下：dp[i][1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，这是很多同学容易陷入的误区。

    达到dp[i][1]状态，有两个具体操作：

    操作一：第i天买入股票了，那么dp[i][1] = dp[i - 1][0] - prices[i]
    操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]
    选最大的，所以 dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);

    同理dp[i][2]也有两个操作：

    操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
    操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]
    所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])
     */
    const length: number = prices.length;
    if (length === 0) return 0;
    const dp: number[][] = new Array(length).fill(0)
        .map(_ => new Array(k * 2 + 1).fill(0));
    // dp[0][j]当j为奇数的时候都初始化为 -prices[0]
    for (let i = 1; i <= k; i++) {
        dp[0][i * 2 - 1] = -prices[0];
    }
    for (let i = 1; i < length; i++) {  // 遍历天数
        for (let j = 1; j < 2 * k + 1; j++) { // 遍历情况
            //  Math.pow(-1, j)根据j的奇偶性决定是买（奇）还是卖（偶）
            // 不管是买还是卖，沿用前一天状态均为dp[i - 1][j]  第i天买/卖操作了 dp[i-1][j-1]代表前一天状态j-1（持有或不持有股票）的最大现金 再加/减当前值
            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + Math.pow(-1, j) * prices[i]);
        }
    }
    return dp[length - 1][2 * k];
};
//leetcode submit region end(Prohibit modification and deletion)
